#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : btree.py
@Time    : 2022/11/25
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 利用列表实现二叉树
"""
from pythonds.basic import Queue


# 基于列表的实现二叉树

def btree(r=None) -> list:
    return [r, [], []]


def insert_left(root: list, new_branch):
    t = root[1]
    root[1] = [new_branch, t, []]


def insert_right(root: list, new_branch):
    t = root[2]
    root[2] = [new_branch, [], t]


def get_left_child(root: list) -> list:
    return root[1]


def get_right_child(root: list) -> list:
    return root[2]


def get_root_val(root: list):
    return root[0]


def set_root_val(root: list, val):
    root[0] = val


def preorder(tree: list):
    if tree:
        print(get_root_val(tree))
        preorder(get_left_child(tree))
        preorder(get_right_child(tree))


def inorder(tree: list):
    if tree:
        inorder(get_left_child(tree))
        print(get_root_val(tree))
        inorder(get_right_child(tree))


def postorder(tree: list):
    if tree:
        postorder(get_left_child(tree))
        postorder(get_right_child(tree))
        print(get_root_val(tree))


def layer_order(tree: list):
    node_queue = Queue()
    node_queue.enqueue(tree)
    while not node_queue.empty():
        node = node_queue.dequeque()
        print(get_root_val(node))
        if get_left_child(node):
            node_queue.enqueue(get_left_child(node))
        if get_right_child(node):
            node_queue.enqueue(get_right_child(node))


def layer_count(tree: list) -> int:
    node_list = [tree]
    layer_list = []

    while node_list:
        next_node_list = []
        used_node_list = []
        while node_list:
            node = node_list.pop(0)
            used_node_list.append(get_root_val(node))
            if get_left_child(node):
                next_node_list.append(get_left_child(node))
            if get_right_child(node):
                next_node_list.append(get_right_child(node))
        node_list = next_node_list
        layer_list.append(used_node_list)
    return len(layer_list)
